package com.caoyanan.algorithm.question.zuoTraining.training004.class05;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeMap;

/**
 *
 * 给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数 据。
 * arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。
 * 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 *
 * 【举例】 matrix ={{2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4},{10,12,5} }
 * 返回: {{1,2,4},{2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5}, {12,14,4}}
 *
 * @author: caoyanan
 * @time: 2021/6/20 13:40
 */
public class Question01_BuildingOutline {

    public static void main(String[] args) {

        int[][] buildings = { {1,2,3}, {2, 3, 5}, {3, 4, 2}, {2 ,5, 1}};
        int[][] contour = findBuildingContour(buildings);
        System.out.println(Arrays.deepToString(contour));
        buildings = new int[][]{{2, 5, 6}, {1, 7, 4}, {4, 6, 7}, {3, 6, 5}, {10, 13, 2}, {9, 11, 3}, {12, 14, 4}, {10, 12, 5}};
        int[][] contour2 = findBuildingContour(buildings);
        System.out.println(Arrays.deepToString(contour2));
    }

    /**
     * 描述大楼轮廓
     * 比如输入的是 { {1,2,3}, {2, 3, 5}, {3, 4, 2}, {2 ,5, 1}}
     * 最终我们需要关注高度的变化，类似于 得到 {[1,3],[2,5],[3,2], [4,1],[5, 0]}的高度变化拐点
     *                                    ___
     *                                ___|  |
     *                               |   |  |___
     *                               |   |  |  |___
     *                            _ _|   |  |  |  |
     *                           0   1   2  3  4  5
     * 所以，一定是要生成一个map, key是x，value是x的最大高度
     * 然后，对于每个x，可能起来，可能落下，可能有多个起来和落下
     * 每一个x点的升高和降落，放到一个小顶堆中，x从小到大，如果x相同，先升高后降落
     * 同时维护一个高度和次数的有序表，如果现在这个x点已经没有高度了，说明这个点是最后的0，否则当前x点的高度就是有序表里的最大值
     *
     * @param arr
     * @return
     */
    private static int[][] findBuildingContour(int[][] arr) {

        // 所有高楼的升起和降落
        PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
        for (int i = 0; i < arr.length; i++) {
            //0 2表示[0]节点升起[2]长度
            heap.add(new Node(arr[i][0], true, arr[i][2]));

            //1 2表示[1]节点降落[2]长度
            heap.add(new Node(arr[i][1], false, arr[i][2]));
        }

        // 高度和次数
        TreeMap<Integer, Integer> heightAndTimes = new TreeMap<>();
        // x节点和最大高度
        TreeMap<Integer, Integer> xAndMaxHeight = new TreeMap<>();
        while (!heap.isEmpty()) {
            Node node = heap.poll();
            if (node.up) {
                if (heightAndTimes.containsKey(node.height)) {
                    heightAndTimes.put(node.height, heightAndTimes.get(node.height) + 1);
                } else {
                    heightAndTimes.put(node.height, 1);
                }
            } else {
                Integer times = heightAndTimes.get(node.height);
                if (times > 1) {
                    heightAndTimes.put(node.height, times - 1);
                } else {
                    heightAndTimes.remove(node.height);
                }
            }

            if (heightAndTimes.isEmpty()) {
                // x 节点的高度都降落了，就是0了
                xAndMaxHeight.put(node.x, 0);
            } else {
                // x节点的最高的高度就是当前最高楼层
                xAndMaxHeight.put(node.x, heightAndTimes.lastKey());
            }
        }

        // 构建答案
        int[][] tmp = new int[arr.length*2][3];
        int preX = 0;
        int preHeight = 0;
        int length = 0;
        Iterator<Map.Entry<Integer, Integer>> iterator = xAndMaxHeight.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            Integer currentX = next.getKey();
            Integer currentHeight = next.getValue();
            if (preHeight == currentHeight) {
                continue;
            }
            if (preHeight != 0) {
                tmp[length++] = new int[]{preX, currentX, preHeight};
            }
            preX = currentX;
            preHeight = currentHeight;
        }
        int[][] answer = new int[length ][3];
        for (int i = 0; i < length; i++) {
            answer[i] = tmp[i];
        }
        return answer;
    }

    public static class NodeComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            if (o1.x != o2.x) {
                return o1.x - o2.x;
            }
            return o1.up ? -1 : 0;
        }
    }

    public static class Node {
        public int x;
        public boolean up;
        private int height;

        public Node(int x, boolean up, int height) {
            this.x = x;
            this.up = up;
            this.height = height;
        }
    }
}
